package merisis.util;

import static java.lang.System.arraycopy;

import java.util.Arrays;

public class BitaSet implements Cloneable {

	private long[] data;

	public BitaSet() {

		data = new long[2];
	}

	public BitaSet(long[] data) {
		this.data = data;
	}

	public void set(long element) {

		long segid = element >>> 6;

		int pos = binarySearch(segid);
		if (pos < 0) {

			pos = -pos;
			pos -= 1;
			pos <<= 1;
			insertSegment(segid, pos);
		} else {

			pos <<= 1;
		}

		int bit = (int) element & 0x3f;
		long bitmask = 1L << bit;
		data[pos + 1] |= bitmask;
	}

	public void setAscendingPoints(long[] elements) {

		int len = elements.length;
		for (int i = 0; i < len; i++) {
			set(elements[i]);
		}
	}

	public void unset(long index) {

		long segid = index >>> 6;

		int pos = binarySearch(segid);
		if (pos < 0) {

			pos = -pos;
			pos -= 1;
			pos <<= 1;
			insertSegment(segid, pos);
		} else {

			pos <<= 1;
		}

		int bit = (int) index & 0x3f;
		long bitmask = 1L << bit;
		data[pos + 1] &= ~bitmask;
	}

	public boolean has(long index) {

		long segid = index >>> 6;

		int pos = binarySearch(segid);
		if (pos < 0)
			return false;

		pos <<= 1;
		int bit = (int) index & 0x3f; // mod 64
		long bitmask = 1L << bit;
		return (data[pos + 1] & bitmask) != 0;
	}

	public boolean isEmpty() {

		int numOfSegment = data.length >>> 1;
		for (int i = 0; i < numOfSegment; i++) {

			if (data[(i << 1) + 1] != 0)
				return false;
		}
		return true;
	}

	public long cardinality() {

		int numOfSegment = data.length >>> 1;
		long countOne = 0;
		for (int i = 0; i < numOfSegment; i++) {

			long bits = data[(i << 1) + 1];
			countOne += BitUtil.countOne(bits);
		}

		return countOne;
	}

	public void union(BitaSet other) {

		long[] dt0, dt1;

		dt0 = data;
		dt1 = other.data;

		int dt0len = dt0.length;
		int dt1len = dt1.length;

		// Draw the map for movement of data,
		// [][0] the postion of this data;
		// [][1] the postion of the other data;
		// [][2] the length of data to move,
		// _____ zero means union only, nonezero means insertation.
		int[][] mvMap = new int[(dt0len + dt1len) >> 1][3];
		int mvSize = 0; // the size of movement.
		int expandedCapacity = 0;
		{
			int i = 0;
			int j = 0;
			L0: while (true) {

				if (dt0[i] < dt1[j]) {

					do {
						i += 2;
						if (i == dt0len) {

							int d = dt1len - j;
							expandedCapacity += d;

							mvMap[mvSize][0] = i;
							mvMap[mvSize][1] = j;
							mvMap[mvSize][2] = d;
							mvSize++;

							break L0;
						}
					} while (dt0[i] < dt1[j]);

				} else if (dt0[i] > dt1[j]) {

					int j0 = j;

					do {
						j += 2;
						if (j == dt1len) {

							int d = j - j0;
							expandedCapacity += d;

							mvMap[mvSize][0] = i;
							mvMap[mvSize][1] = j0;
							mvMap[mvSize][2] = d;
							mvSize++;

							break L0;
						}
					} while (dt0[i] > dt1[j]);

					int d = j - j0;
					expandedCapacity += d;

					mvMap[mvSize][0] = i;
					mvMap[mvSize][1] = j0;
					mvMap[mvSize][2] = d;
					mvSize++;

				} else {
					mvMap[mvSize][0] = i;
					mvMap[mvSize][1] = j;
					mvMap[mvSize][2] = 0;
					mvSize++;

					j += 2;
					if (j == dt1len)
						break L0;

					i += 2;
					if (i == dt0len) {

						// Reaching the end of dt0,
						// moves the left data of dt1
						int d = dt1len - j;
						expandedCapacity += d;

						mvMap[mvSize][0] = i;
						mvMap[mvSize][1] = j;
						mvMap[mvSize][2] = d;
						mvSize++;

						break L0;
					}
				}
			}
		}

		for (int r = 0; r < mvSize; r++) {
			System.out.println("move: " + Arrays.toString(mvMap[r]));
		}

		if (expandedCapacity == 0) {

			for (int r = 0; r < mvMap.length; r++) {
				dt0[mvMap[r][0] + 1] |= dt1[mvMap[r][1] + 1];
			}
			return;
		}

		int dtnlen = dt0len + expandedCapacity;
		long[] ndata = new long[dtnlen];

		// fill new data, copy from this object and preserve spaces for
		// the insertation from the other object
		{
			int tail = dt0len - 1;
			for (int r = mvSize - 1; r >= 0; r--) {

				if (mvMap[r][2] == 0)
					continue;

				int pos = mvMap[r][0];
				int offset = mvMap[r][2];
				arraycopy(dt0, pos, ndata, pos + offset, tail - pos + 1);
				tail = pos - 1;
			}

			if (tail >= 0) {
				arraycopy(dt0, 0, ndata, 0, tail + 1);
			}
		}

		// union segment and fill the preserved data
		{
			int adjust = 0; // the adjustment for moves
			for (int r = 0; r < mvSize; r++) {

				if (mvMap[r][2] == 0) {

					// union the segments
					ndata[mvMap[r][0] + adjust + 1] |= dt1[mvMap[r][1] + 1];
				} else {

					int len = mvMap[r][2];

					arraycopy(dt1, mvMap[r][1], ndata, mvMap[r][0] + adjust,
							len);

					adjust += len;
				}
			}
		}

		this.data = ndata;
	}

	public void intersect(BitaSet other) {

		long[] dt0, dt1;

		dt0 = data;
		dt1 = other.data;

		int dt0len = dt0.length;
		int dt1len = dt1.length;

		int i = 0;
		int j = 0;
		L0: while (true) {

			if (dt0[i] < dt1[j]) {

				do {
					dt0[i + 1] = 0; // zero

					i += 2;
					if (i == dt0len) {
						break L0;
					}
				} while (dt0[i] < dt1[j]);

			} else if (dt0[i] > dt1[j]) {

				do {
					j += 2;
					if (j == dt1len) {

						// all of the remainings are reset with 0;
						do {
							dt0[i + 1] = 0; // zero
							i += 2;
						} while (i < dt0len);

						break L0;
					}
				} while (dt0[i] > dt1[j]);
			} else {
				dt0[i + 1] &= dt1[j + 1];

				i += 2;
				if (i == dt0len)
					break L0;

				j += 2;
				if (j == dt1len) {
					do {
						dt0[i + 1] = 0; // zero
						i += 2;
					} while (i < dt0len);

					break L0;
				}
			}
		}
	}

	public void remove(BitaSet other) {
		long[] dt0, dt1;

		dt0 = data;
		dt1 = other.data;

		int dt0len = dt0.length;
		int dt1len = dt1.length;

		int i = 0;
		int j = 0;
		L0: while (true) {

			if (dt0[i] < dt1[j]) {

				do {
					i += 2;
					if (i == dt0len)
						break L0;
				} while (dt0[i] < dt1[j]);

			} else if (dt0[i] > dt1[j]) {

				do {
					j += 2;
					if (j == dt1len)
						break L0;
				} while (dt0[i] > dt1[j]);
			} else {
				dt0[i + 1] &= ~dt1[j + 1];

				i += 2;
				if (i >= dt0len)
					break L0;

				j += 2;
				if (j >= dt1len)
					break L0;
			}
		}
	}

	public Object clone() {

		try {
			BitaSet obs = (BitaSet) super.clone();
			obs.data = obs.data.clone();

			return obs;
		} catch (CloneNotSupportedException e) {
			throw new RuntimeException(e);
		}
	}

	public long[] getBitData() {
		return data;
	}

	public void setBitData(long[] data) {
		this.data = data;
	}

	public BitaSetIterator iterator(final long posOfStart) {

		int idx = binarySearch(posOfStart >>> 6);
		final int wordbitIndex;
		if (idx < 0) {

			idx = -idx;
			wordbitIndex = 0;
		} else {
			wordbitIndex = (int) (posOfStart & 0x3f);
		}
		idx <<= 1;

		final int segmentIndex = idx;

		return new BitaSetIterator() {

			int segidx = segmentIndex;
			int bitIdx = wordbitIndex;

			public long next() {

				if (bitIdx == 64) {
					segidx += 2;
					if (segidx == data.length)
						return -1;

					bitIdx = 0;
				}

				while (data[segidx + 1] == 0) {
					segidx += 2;
					if (segidx == data.length)
						return -1;
				}

				long bits = data[segidx + 1] >>> bitIdx;
				if (bits != 0) {
					bitIdx += BitUtil.ntz(bits);
					long r = (data[segidx] << 6) + bitIdx;
					bitIdx++;
					return r;
				}

				do {
					segidx += 2;
					if (segidx == data.length)
						return -1;

				} while (data[segidx + 1] == 0);

				bitIdx = BitUtil.ntz(data[segidx + 1]);

				long r = (data[segidx] << 6) + bitIdx;
				bitIdx++;

				return r;
			}
			
			public void unset() {
				throw new UnsupportedOperationException();
			}
		};
	}
	
	public BitaSetIterator iteratorInversed() {
		throw new UnsupportedOperationException("To be supported in the future");
	}

	public BitaSetIterator iteratorInversed(final long posOfStart) {
		// TODO
		throw new UnsupportedOperationException("To be supported in the future");
	}

	/**
	 * Copy a subsect.
	 * 
	 * @param from
	 * @param to
	 * @return
	 */
	public BitaSet subsect(long from, long to) {

		// TODO
		throw new UnsupportedOperationException("To be supported in the future");
	}

	public boolean subsetOf(BitaSet other) {

		// TODO
		throw new UnsupportedOperationException("To be supported in the future");
	}

	@Override
	public boolean equals(Object obj) {

		if (this == obj)
			return true;

		if (!(obj instanceof BitaSet))
			return false;

		long[] dt1 = ((BitaSet) obj).data;

		int i = data.length - 2;
		int j = dt1.length - 2;

		while (i >= 0 && j >= 0) {

			if (data[i + 1] == 0) {
				i -= 2;
				continue;
			}

			long segid0 = data[i];
			long segid1 = dt1[j];

			if (segid0 > segid1) {
				return false;
			} else if (segid0 < segid1) {
				if (dt1[j + 1] == 0) {
					do {
						j -= 2;
						if (j < 0 || segid0 > dt1[j])
							return false;
					} while (dt1[j + 1] == 0);

					if (segid0 != dt1[j])
						return false;

					if ((data[i + 1] ^ dt1[j + 1]) > 0)
						return false;

					j -= 2;
					if (j < 0)
						return false;
				} else
					return false;

			} else {
				if ((data[i + 1] ^ dt1[j + 1]) > 0)
					return false;

				j -= 2;

			}
			i -= 2;
		}

		if (i >= 0 || j >= 0)
			return false;

		return true;
	}

	@Override
	public int hashCode() {

		long h = 0x98761234; // something non-zero for length==0
		for (int i = data.length - 2; i >= 0; i -= 2) {

			if (data[i + 1] == 0)
				continue; // The empty segment must be ignored.

			h ^= data[i];
			h = (h << 1) | (h >>> 31); // rotate left

			h ^= data[i + 1];
			h = (h << 1) | (h >>> 31); // rotate left
		}

		return (int) ((h >> 32) ^ h); // fold leftmost bits into right
	}

	private int binarySearch(long key) {

		int low = 0;
		int high = (data.length - 1) >>> 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
			long midVal = data[mid << 1];

			if (midVal < key)
				low = mid + 1;
			else if (midVal > key)
				high = mid - 1;
			else
				return mid; // key found
		}
		return -(low + 1); // key not found.
	}

	private void insertSegment(long segid, int pos) {

		long[] r;

		int srclen = data.length;

		r = new long[srclen + 2];

		if (pos == 0) {

			r[0] = segid;
			r[1] = 0;
			System.arraycopy(data, 0, r, 1, srclen);
		} else if (pos == srclen) {

			r[srclen] = segid;
			System.arraycopy(data, 0, r, 0, srclen);
		} else {

			System.arraycopy(data, 0, r, 0, pos + 1);
			r[pos] = segid;
			r[pos + 1] = 0;
			System.arraycopy(data, pos, r, pos + 2, srclen - pos);
		}

		data = r;
	}
}